package com.zjj.lbw.algorithm.dp;

/**
 * @author zhanglei.zjj
 * @description leetcode_416. 分割等和子集
 * 给你一个 只包含正整数 的 非空 数组nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,5,11,5]
 * 输出：true
 * 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
 * 示例 2：
 * <p>
 * 输入：nums = [1,2,3,5]
 * 输出：false
 * 解释：数组不能分割成两个元素和相等的子集。
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length <= 200
 * 1 <= nums[i] <= 100
 * @date 2023/7/9 21:40
 */
public class PartitionEqSubsetSum_leetcode_416 {
    // 一维dp数组实现
    public boolean canPartition(int[] nums) {
        int n = nums.length;

        // 数组元素只有0个或者1个直接返回false
        if (n < 2) {
            return false;
        }
        // 数组元素只有两个直接判断
        if (n == 2) {
            return nums[0] == nums[1] ? true : false;
        }

        // 统计数组和，以及最大值
        int sum = 0;
        int maxNum = 0;
        for (int num : nums) {
            sum += num;
            maxNum = Math.max(maxNum, num);
        }

        // 奇数直接返回false
        if (sum % 2 != 0) {
            return false;
        }

        int target = sum / 2;
        // 数组最大元素大于数组和的一半，是不能等分为相等的两个子集
        if (maxNum > target) {
            return false;
        }

        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int i = 0; i < n; i++) {
            for (int j = target; j >= nums[i]; j--) {
                // 数组存在元素大于数组元素和的一半，是不可能分为和相等的两个子集
                // 数组存在元素等于数组元素和的一半，一定可以分为相等的两个子集
                if (nums[i] >= target) {
                    return nums[i] > target ? false : true;
                }
                dp[j] = dp[j] || dp[j - nums[i]];
            }
        }

        return dp[target];
    }

    // 二维dp数组实现
    public boolean canPartition2(int[] nums) {
        int n = nums.length;

        // 数组元素只有0个或者1个直接返回false
        if (n < 2) {
            return false;
        }
        // 数组元素只有两个直接判断
        if (n == 2) {
            return nums[0] == nums[1] ? true : false;
        }

        // 统计数组和，以及最大值
        int sum = 0;
        int maxNum = 0;
        for (int num : nums) {
            sum += num;
            maxNum = Math.max(maxNum, num);
        }

        // 奇数直接返回false
        if (sum % 2 != 0) {
            return false;
        }

        int target = sum / 2;
        // 数组最大元素大于数组和的一半，是不能等分为相等的两个子集
        if (maxNum > target) {
            return false;
        }
        boolean[][] dp = new boolean[n + 1][target + 1];
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= target; j++) {
                // 数组存在元素大于数组元素和的一半，是不可能分为和相等的两个子集
                // 数组存在元素等于数组元素和的一半，一定可以分为相等的两个子集
                if (nums[i - 1] >= target) {
                    return nums[i - 1] > target ? false : true;
                }

                // 如果当前元素是小于目标和，当前元素可以选取
                // 就有用当前元素和不用两种情况
                if (j >= nums[i - 1]) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[n][target];
    }

    public static void main(String[] args) {
        new PartitionEqSubsetSum_leetcode_416().canPartition2(new int[]{1, 5, 11, 5});
    }
}
